#ifndef __STACK_H__
#define __STACK_H__

#include "linkedlist.h"

#include <exception>

namespace algo
{

class empty_stack : std::exception
{
public:
	const char* what() const throw()
	{
		return "empty stack";
	}
};

template<typename T>
class Stack
{
public:
	Stack():m_capacity(50) {}
	Stack(int capacity):m_capacity(capacity) {}

	virtual bool push(const T &val);
	virtual bool pop(T &val);
	virtual std::shared_ptr<T> pop();
	virtual T& top();

	virtual int size();
    virtual bool isEmpty();

private:
	int m_capacity;
	LinkedList<T> m_linkedlist;
};

template<typename T>
bool Stack<T>::push(const T &val)
{
	if (m_linkedlist.size() > m_capacity)
	{
		return false;
	}

	m_linkedlist.add(val);
	return true;
}

template<typename T>
bool Stack<T>::pop(T &val)
{
	if (isEmpty())
	{
		throw empty_stack();
	}

	val = m_linkedlist.getLastNode()->val;
	m_linkedlist.removeLast();

	return true;
}

template<typename T>
std::shared_ptr<T> Stack<T>::pop()
{
	if (isEmpty())
	{
		throw empty_stack();
	}

	std::shared_ptr<T> res(std::make_shared<T>(std::move(m_linkedlist.getLastNode()->val)));
	m_linkedlist.removeLast();

	return res;
}

template<typename T>
T& Stack<T>::top()
{
	if (isEmpty())
	{
		throw empty_stack();
	}

	return m_linkedlist.getLastNode()->val;
}

template<typename T>
int Stack<T>::size()
{
	return m_linkedlist.size();
}

template<typename T>
bool Stack<T>::isEmpty()
{
	return m_linkedlist.isEmpty();
}

}	//namespace end

#endif




